package linear_list.dlistwithhead;

public class DoubleLinckedList {
    private int size;
    private Node head;
    private Node tail;

    @Override
    public String toString() {
        String str = "";
        Node pNode = head;
        while(pNode != null){
            str += pNode.val + "->";
            pNode = pNode.next;
        }
        str += "NULL";
        return str;
    }

    /**
     * 链表的插入
     * @param val
     */
    //头插
    public void addFirst(int val){
        Node newnode = new Node(null,val,head);
        if(head == null){
            tail = newnode;
        }else{
            head.prev = newnode;
        }
        head = newnode;
        size++;
    }
    //尾插
    public void addLast(int val){
        Node newnode = new Node(tail,val,null);
        if(tail == null){
           head = newnode;
        }else{
            tail.next = newnode;
        }
        tail = newnode;
        size++;
    }
    //按下标插入
    public void addInsert(int index,int val) {
        if (index < 0 || index > size) {
            System.err.println("input error");
            return;
        }
        if (index == 0) {
            addFirst(val);
        } else if (index == size) {
            addLast(val);
        } else {
            Node prevNode = findNode(index);
            Node newnode = new Node(prevNode, val, prevNode.next);
            prevNode.next.prev = newnode;
            prevNode.next = newnode;
            size++;
        }
    }
    //根据下标找到结点的前驱结点
    public Node findNode(int index){
        Node pNode;
        if(index < size >> 1){
            pNode = head;
            for (int i = 0; i < index - 1; i++) {
                pNode = pNode.next;
            }
        }else{
            pNode = tail;
            for (int i = 0; i < size - index; i++) {
                pNode = pNode.prev;
            }
        }
        return pNode;
    }

    /**
     * 查找
     */
    public int get(int index){
        if(index < 0 || index >= size){
            System.err.println("input error");
            return -1;
        }
        Node pNode = findNode(index + 1);
        return pNode.val;
    }

    public boolean contains(int val){
        Node pNode = head;
        while(pNode != null){
            if(pNode.val == val){
                return true;
            }
            pNode = pNode.next;
        }
        return false;
    }

    /**
     * 修改
     */
    public int set(int index,int val){
        if(index < 0 || index >= size){
            System.err.println("input error");
            return -1;
        }
        Node pNode = findNode(index + 1);
        int ret = pNode.val;
        pNode.val = val;
        return ret;
    }

    /**
     * 删除
     */
    public void removeIndex(int index){
        if(index < 0 || index >= size){
            System.err.println("input error");
            return;
        }
        unlink(findNode(index + 1));
    }

    public void removeFirst(){
        removeIndex(0);
    }

    public void removeLast(){
        removeIndex(size - 1);
    }

    public void removeValueOnce(int val){
        Node pNode = head;
        while(pNode != null){
            if(pNode.val == val){
                unlink(pNode);
                break;
            }
            pNode = pNode.next;
        }
    }

    public void removeAllvalue(int val){
        Node pNode = head;
        while(pNode != null){
            if(pNode.val == val){
                Node temp = pNode.next;
                unlink(pNode);
                pNode = temp;
            }else {
                pNode = pNode.next;
            }
        }
    }
    //脱钩操作
    public void unlink(Node pNode){
        Node prev = pNode.prev;
        Node next = pNode.next;
        //前
        if(prev == null){
            head = next;
        }else{
            prev.next = next;
            pNode.prev = null;
        }
        //后
        if(next == null){
            tail = prev;
        }else{
            next.prev = prev;
            pNode.next = null;
        }
        size--;
    }
}

class Node{
    Node prev;
    int val;
    Node next;
    public Node(int val) {
        this.val = val;
    }
    public Node(Node prev, int val, Node next) {
        this.prev = prev;
        this.val = val;
        this.next = next;
    }
}